1. Field of the Invention
The present invention relates, in general, to a variable length code demodulating apparatus. In particular it relates to a variable length code demodulating apparatus suited for image data compression.
2. Description of the Related Art
Recently, some remarkable progress has been made in image data compression techniques. In such image data compression techniques, in order to raise the efficiency of digital transmission and recording etc., the image data is encoded with a smaller bit rate. Examples of this technique are the predictive coding technique and transform coding technique, etc. These techniques are described in detail in "Multidimensional Processing of TV Pictures", by T. Fukinuki, published by Nikkan Kogyo Shinbunsha, Jun. 25, 1984, incorporated herein by reference. In addition, a further image data compression can be achieved by performing variable length encoding on the code compressed by such encoding processes. The variable length encoding consists in varying the encoded bit width in accordance with the frequency of occurrence of the code. By this means, a smaller bit rate can be obtained than with fixed length coding.
Next, as an example of variable length coding, a description will be given with reference to FIGS. 3a and 3b of a method of generating Huffman codes. Let us know assume that t fixed length codes S.sub.1, S.sub.1, . . . S.sub.t are converted into Huffman codes. FIGS. 3a and 3b show an example for the case where t=6. First of all, these codes S.sub.1 to S.sub.6 are arranged in order of the magnitude of the frequency of their occurrence (the probability of occurrence). The probabilities of occurrence of codes S.sub.1 to S.sub.6 are respectively 0.35, 0.20, 0.15, 0.15, 0.10 and 0.05 as shown in FIG. 3a. They are therefore arranged in the order of codes S.sub.1 to S.sub.6. Next, taking the two codes whose probability of occurrence is smallest as one group, their composite probability (the sum of the two probabilities of occurrence) is found. In FIG. 3a, codes S.sub.6 and S.sub.5 have the smallest probability of occurrence, and their composite probability is 0.15. Next, this group and the other codes are arranged in order of magnitude of their probabilities of occurrence (or composite probability). The two codes (or groups) whose probability of occurrence (or composite probability) is smallest are taken as a new group, and the composite probability of this group is found. Subsequently, this process is repeated until a relisting with the composite probability of 1 has been effected as shown in FIG. 3a.
Next, using FIG. 3a, a code tree as shown in FIG. 3b is compiled. "0" and "1" are then allocated in accordance with the branching of this code tree. In FIG. 3b, the upper branches are allocated "0", while the lower branches are allocated "1". The Huffman codes are obtained by following this branching. For example, as shown by the thick line in FIG. 3b, the fixed length code S.sub.4 passes along a branch "0", along a branch "1", and finally along a branch "0", so it is converted to the Huffman code "010". The Huffman codes of the codes S.sub.1 to S.sub.56 found in this way are shown in Table 1 below.
TABLE 1 ______________________________________ Code Huffman code Code Huffman Code ______________________________________ S.sub.1 00 S.sub.4 010 S.sub.2 10 S.sub.5 0110 S.sub.3 11 S.sub.6 0111 ______________________________________
As shown in Table 1, codes whose probability of occurrence is high are converted into Huffman codes of short bit length, while codes whose probability of occurrence is low are converted into Huffman codes of longer bit length. In this way, the overall bit rate can be reduced.
In general, to demodulate such variable length code into fixed length code, a conversion table embedded in a solid state memory such as a ROM is used. In FIG. 3a, for convenience in explanation, the maximum bit number of the variable length code (huffman code) was taken as being 4 bits, but, in an actual image data signal, the maximum bit number is very large, for example, 15 bits.
Accordingly, some proposals have been made to reduce the capacity of the conversion table. As an example, this type of variable length code demodulating apparatus is described in Japanese Patent Disclosure (Kodai) No. 63-52578. This technique discloses that the bit length of coded data which is input is set as one n-th of the maximum bit length of coded data, and the conversion table is read out n times. Thus, the capacity of the conversion table can be reduced.
In the variable length code demodulating apparatus described above, however, a Run-Length code is used in which two values are employed consisting of while and black. Such a technique requires a long transaction time for conversion due to numerous read outs of the conversion table.